home *** CD-ROM | disk | FTP | other *** search
/ PCGUIA 127 / PC Guia 127.iso / Software / Produtividade / OpenOffice.org 2.0.1 / openofficeorg4.cab / pyassem.py < prev    next >
Text File  |  2005-11-19  |  26KB  |  819 lines
  1. """A flow graph representation for Python bytecode"""
  2.  
  3. import dis
  4. import new
  5. import sys
  6. import types
  7.  
  8. from compiler import misc
  9. from compiler.consts \
  10.      import CO_OPTIMIZED, CO_NEWLOCALS, CO_VARARGS, CO_VARKEYWORDS
  11.  
  12. class FlowGraph:
  13.     def __init__(self):
  14.         self.current = self.entry = Block()
  15.         self.exit = Block("exit")
  16.         self.blocks = misc.Set()
  17.         self.blocks.add(self.entry)
  18.         self.blocks.add(self.exit)
  19.  
  20.     def startBlock(self, block):
  21.         if self._debug:
  22.             if self.current:
  23.                 print "end", repr(self.current)
  24.                 print "    next", self.current.next
  25.                 print "   ", self.current.get_children()
  26.             print repr(block)
  27.         self.current = block
  28.  
  29.     def nextBlock(self, block=None):
  30.         # XXX think we need to specify when there is implicit transfer
  31.         # from one block to the next.  might be better to represent this
  32.         # with explicit JUMP_ABSOLUTE instructions that are optimized
  33.         # out when they are unnecessary.
  34.         #
  35.         # I think this strategy works: each block has a child
  36.         # designated as "next" which is returned as the last of the
  37.         # children.  because the nodes in a graph are emitted in
  38.         # reverse post order, the "next" block will always be emitted
  39.         # immediately after its parent.
  40.         # Worry: maintaining this invariant could be tricky
  41.         if block is None:
  42.             block = self.newBlock()
  43.  
  44.         # Note: If the current block ends with an unconditional
  45.         # control transfer, then it is incorrect to add an implicit
  46.         # transfer to the block graph.  The current code requires
  47.         # these edges to get the blocks emitted in the right order,
  48.         # however. :-(  If a client needs to remove these edges, call
  49.         # pruneEdges().
  50.  
  51.         self.current.addNext(block)
  52.         self.startBlock(block)
  53.  
  54.     def newBlock(self):
  55.         b = Block()
  56.         self.blocks.add(b)
  57.         return b
  58.  
  59.     def startExitBlock(self):
  60.         self.startBlock(self.exit)
  61.  
  62.     _debug = 0
  63.  
  64.     def _enable_debug(self):
  65.         self._debug = 1
  66.  
  67.     def _disable_debug(self):
  68.         self._debug = 0
  69.  
  70.     def emit(self, *inst):
  71.         if self._debug:
  72.             print "\t", inst
  73.         if inst[0] in ['RETURN_VALUE', 'YIELD_VALUE']:
  74.             self.current.addOutEdge(self.exit)
  75.         if len(inst) == 2 and isinstance(inst[1], Block):
  76.             self.current.addOutEdge(inst[1])
  77.         self.current.emit(inst)
  78.  
  79.     def getBlocksInOrder(self):
  80.         """Return the blocks in reverse postorder
  81.  
  82.         i.e. each node appears before all of its successors
  83.         """
  84.         # XXX make sure every node that doesn't have an explicit next
  85.         # is set so that next points to exit
  86.         for b in self.blocks.elements():
  87.             if b is self.exit:
  88.                 continue
  89.             if not b.next:
  90.                 b.addNext(self.exit)
  91.         order = dfs_postorder(self.entry, {})
  92.         order.reverse()
  93.         self.fixupOrder(order, self.exit)
  94.         # hack alert
  95.         if not self.exit in order:
  96.             order.append(self.exit)
  97.  
  98.         return order
  99.  
  100.     def fixupOrder(self, blocks, default_next):
  101.         """Fixup bad order introduced by DFS."""
  102.  
  103.         # XXX This is a total mess.  There must be a better way to get
  104.         # the code blocks in the right order.
  105.  
  106.         self.fixupOrderHonorNext(blocks, default_next)
  107.         self.fixupOrderForward(blocks, default_next)
  108.  
  109.     def fixupOrderHonorNext(self, blocks, default_next):
  110.         """Fix one problem with DFS.
  111.  
  112.         The DFS uses child block, but doesn't know about the special
  113.         "next" block.  As a result, the DFS can order blocks so that a
  114.         block isn't next to the right block for implicit control
  115.         transfers.
  116.         """
  117.         index = {}
  118.         for i in range(len(blocks)):
  119.             index[blocks[i]] = i
  120.  
  121.         for i in range(0, len(blocks) - 1):
  122.             b = blocks[i]
  123.             n = blocks[i + 1]
  124.             if not b.next or b.next[0] == default_next or b.next[0] == n:
  125.                 continue
  126.             # The blocks are in the wrong order.  Find the chain of
  127.             # blocks to insert where they belong.
  128.             cur = b
  129.             chain = []
  130.             elt = cur
  131.             while elt.next and elt.next[0] != default_next:
  132.                 chain.append(elt.next[0])
  133.                 elt = elt.next[0]
  134.             # Now remove the blocks in the chain from the current
  135.             # block list, so that they can be re-inserted.
  136.             l = []
  137.             for b in chain:
  138.                 assert index[b] > i
  139.                 l.append((index[b], b))
  140.             l.sort()
  141.             l.reverse()
  142.             for j, b in l:
  143.                 del blocks[index[b]]
  144.             # Insert the chain in the proper location
  145.             blocks[i:i + 1] = [cur] + chain
  146.             # Finally, re-compute the block indexes
  147.             for i in range(len(blocks)):
  148.                 index[blocks[i]] = i
  149.  
  150.     def fixupOrderForward(self, blocks, default_next):
  151.         """Make sure all JUMP_FORWARDs jump forward"""
  152.         index = {}
  153.         chains = []
  154.         cur = []
  155.         for b in blocks:
  156.             index[b] = len(chains)
  157.             cur.append(b)
  158.             if b.next and b.next[0] == default_next:
  159.                 chains.append(cur)
  160.                 cur = []
  161.         chains.append(cur)
  162.  
  163.         while 1:
  164.             constraints = []
  165.  
  166.             for i in range(len(chains)):
  167.                 l = chains[i]
  168.                 for b in l:
  169.                     for c in b.get_children():
  170.                         if index[c] < i:
  171.                             forward_p = 0
  172.                             for inst in b.insts:
  173.                                 if inst[0] == 'JUMP_FORWARD':
  174.                                     if inst[1] == c:
  175.                                         forward_p = 1
  176.                             if not forward_p:
  177.                                 continue
  178.                             constraints.append((index[c], i))
  179.  
  180.             if not constraints:
  181.                 break
  182.  
  183.             # XXX just do one for now
  184.             # do swaps to get things in the right order
  185.             goes_before, a_chain = constraints[0]
  186.             assert a_chain > goes_before
  187.             c = chains[a_chain]
  188.             chains.remove(c)
  189.             chains.insert(goes_before, c)
  190.  
  191.         del blocks[:]
  192.         for c in chains:
  193.             for b in c:
  194.                 blocks.append(b)
  195.  
  196.     def getBlocks(self):
  197.         return self.blocks.elements()
  198.  
  199.     def getRoot(self):
  200.         """Return nodes appropriate for use with dominator"""
  201.         return self.entry
  202.  
  203.     def getContainedGraphs(self):
  204.         l = []
  205.         for b in self.getBlocks():
  206.             l.extend(b.getContainedGraphs())
  207.         return l
  208.  
  209. def dfs_postorder(b, seen):
  210.     """Depth-first search of tree rooted at b, return in postorder"""
  211.     order = []
  212.     seen[b] = b
  213.     for c in b.get_children():
  214.         if seen.has_key(c):
  215.             continue
  216.         order = order + dfs_postorder(c, seen)
  217.     order.append(b)
  218.     return order
  219.  
  220. class Block:
  221.     _count = 0
  222.  
  223.     def __init__(self, label=''):
  224.         self.insts = []
  225.         self.inEdges = misc.Set()
  226.         self.outEdges = misc.Set()
  227.         self.label = label
  228.         self.bid = Block._count
  229.         self.next = []
  230.         Block._count = Block._count + 1
  231.  
  232.     def __repr__(self):
  233.         if self.label:
  234.             return "<block %s id=%d>" % (self.label, self.bid)
  235.         else:
  236.             return "<block id=%d>" % (self.bid)
  237.  
  238.     def __str__(self):
  239.         insts = map(str, self.insts)
  240.         return "<block %s %d:\n%s>" % (self.label, self.bid,
  241.                                        '\n'.join(insts))
  242.  
  243.     def emit(self, inst):
  244.         op = inst[0]
  245.         if op[:4] == 'JUMP':
  246.             self.outEdges.add(inst[1])
  247.         self.insts.append(inst)
  248.  
  249.     def getInstructions(self):
  250.         return self.insts
  251.  
  252.     def addInEdge(self, block):
  253.         self.inEdges.add(block)
  254.  
  255.     def addOutEdge(self, block):
  256.         self.outEdges.add(block)
  257.  
  258.     def addNext(self, block):
  259.         self.next.append(block)
  260.         assert len(self.next) == 1, map(str, self.next)
  261.  
  262.     _uncond_transfer = ('RETURN_VALUE', 'RAISE_VARARGS', 'YIELD_VALUE',
  263.                         'JUMP_ABSOLUTE', 'JUMP_FORWARD', 'CONTINUE_LOOP')
  264.  
  265.     def pruneNext(self):
  266.         """Remove bogus edge for unconditional transfers
  267.  
  268.         Each block has a next edge that accounts for implicit control
  269.         transfers, e.g. from a JUMP_IF_FALSE to the block that will be
  270.         executed if the test is true.
  271.  
  272.         These edges must remain for the current assembler code to
  273.         work. If they are removed, the dfs_postorder gets things in
  274.         weird orders.  However, they shouldn't be there for other
  275.         purposes, e.g. conversion to SSA form.  This method will
  276.         remove the next edge when it follows an unconditional control
  277.         transfer.
  278.         """
  279.         try:
  280.             op, arg = self.insts[-1]
  281.         except (IndexError, ValueError):
  282.             return
  283.         if op in self._uncond_transfer:
  284.             self.next = []
  285.  
  286.     def get_children(self):
  287.         if self.next and self.next[0] in self.outEdges:
  288.             self.outEdges.remove(self.next[0])
  289.         return self.outEdges.elements() + self.next
  290.  
  291.     def getContainedGraphs(self):
  292.         """Return all graphs contained within this block.
  293.  
  294.         For example, a MAKE_FUNCTION block will contain a reference to
  295.         the graph for the function body.
  296.         """
  297.         contained = []
  298.         for inst in self.insts:
  299.             if len(inst) == 1:
  300.                 continue
  301.             op = inst[1]
  302.             if hasattr(op, 'graph'):
  303.                 contained.append(op.graph)
  304.         return contained
  305.  
  306. # flags for code objects
  307.  
  308. # the FlowGraph is transformed in place; it exists in one of these states
  309. RAW = "RAW"
  310. FLAT = "FLAT"
  311. CONV = "CONV"
  312. DONE = "DONE"
  313.  
  314. class PyFlowGraph(FlowGraph):
  315.     super_init = FlowGraph.__init__
  316.  
  317.     def __init__(self, name, filename, args=(), optimized=0, klass=None):
  318.         self.super_init()
  319.         self.name = name
  320.         self.filename = filename
  321.         self.docstring = None
  322.         self.args = args # XXX
  323.         self.argcount = getArgCount(args)
  324.         self.klass = klass
  325.         if optimized:
  326.             self.flags = CO_OPTIMIZED | CO_NEWLOCALS
  327.         else:
  328.             self.flags = 0
  329.         self.consts = []
  330.         self.names = []
  331.         # Free variables found by the symbol table scan, including
  332.         # variables used only in nested scopes, are included here.
  333.         self.freevars = []
  334.         self.cellvars = []
  335.         # The closure list is used to track the order of cell
  336.         # variables and free variables in the resulting code object.
  337.         # The offsets used by LOAD_CLOSURE/LOAD_DEREF refer to both
  338.         # kinds of variables.
  339.         self.closure = []
  340.         self.varnames = list(args) or []
  341.         for i in range(len(self.varnames)):
  342.             var = self.varnames[i]
  343.             if isinstance(var, TupleArg):
  344.                 self.varnames[i] = var.getName()
  345.         self.stage = RAW
  346.  
  347.     def setDocstring(self, doc):
  348.         self.docstring = doc
  349.  
  350.     def setFlag(self, flag):
  351.         self.flags = self.flags | flag
  352.         if flag == CO_VARARGS:
  353.             self.argcount = self.argcount - 1
  354.  
  355.     def checkFlag(self, flag):
  356.         if self.flags & flag:
  357.             return 1
  358.  
  359.     def setFreeVars(self, names):
  360.         self.freevars = list(names)
  361.  
  362.     def setCellVars(self, names):
  363.         self.cellvars = names
  364.  
  365.     def getCode(self):
  366.         """Get a Python code object"""
  367.         if self.stage == RAW:
  368.             self.computeStackDepth()
  369.             self.flattenGraph()
  370.         if self.stage == FLAT:
  371.             self.convertArgs()
  372.         if self.stage == CONV:
  373.             self.makeByteCode()
  374.         if self.stage == DONE:
  375.             return self.newCodeObject()
  376.         raise RuntimeError, "inconsistent PyFlowGraph state"
  377.  
  378.     def dump(self, io=None):
  379.         if io:
  380.             save = sys.stdout
  381.             sys.stdout = io
  382.         pc = 0
  383.         for t in self.insts:
  384.             opname = t[0]
  385.             if opname == "SET_LINENO":
  386.                 print
  387.             if len(t) == 1:
  388.                 print "\t", "%3d" % pc, opname
  389.                 pc = pc + 1
  390.             else:
  391.                 print "\t", "%3d" % pc, opname, t[1]
  392.                 pc = pc + 3
  393.         if io:
  394.             sys.stdout = save
  395.  
  396.     def computeStackDepth(self):
  397.         """Compute the max stack depth.
  398.  
  399.         Approach is to compute the stack effect of each basic block.
  400.         Then find the path through the code with the largest total
  401.         effect.
  402.         """
  403.         depth = {}
  404.         exit = None
  405.         for b in self.getBlocks():
  406.             depth[b] = findDepth(b.getInstructions())
  407.  
  408.         seen = {}
  409.  
  410.         def max_depth(b, d):
  411.             if seen.has_key(b):
  412.                 return d
  413.             seen[b] = 1
  414.             d = d + depth[b]
  415.             children = b.get_children()
  416.             if children:
  417.                 return max([max_depth(c, d) for c in children])
  418.             else:
  419.                 if not b.label == "exit":
  420.                     return max_depth(self.exit, d)
  421.                 else:
  422.                     return d
  423.  
  424.         self.stacksize = max_depth(self.entry, 0)
  425.  
  426.     def flattenGraph(self):
  427.         """Arrange the blocks in order and resolve jumps"""
  428.         assert self.stage == RAW
  429.         self.insts = insts = []
  430.         pc = 0
  431.         begin = {}
  432.         end = {}
  433.         for b in self.getBlocksInOrder():
  434.             begin[b] = pc
  435.             for inst in b.getInstructions():
  436.                 insts.append(inst)
  437.                 if len(inst) == 1:
  438.                     pc = pc + 1
  439.                 elif inst[0] != "SET_LINENO":
  440.                     # arg takes 2 bytes
  441.                     pc = pc + 3
  442.             end[b] = pc
  443.         pc = 0
  444.         for i in range(len(insts)):
  445.             inst = insts[i]
  446.             if len(inst) == 1:
  447.                 pc = pc + 1
  448.             elif inst[0] != "SET_LINENO":
  449.                 pc = pc + 3
  450.             opname = inst[0]
  451.             if self.hasjrel.has_elt(opname):
  452.                 oparg = inst[1]
  453.                 offset = begin[oparg] - pc
  454.                 insts[i] = opname, offset
  455.             elif self.hasjabs.has_elt(opname):
  456.                 insts[i] = opname, begin[inst[1]]
  457.         self.stage = FLAT
  458.  
  459.     hasjrel = misc.Set()
  460.     for i in dis.hasjrel:
  461.         hasjrel.add(dis.opname[i])
  462.     hasjabs = misc.Set()
  463.     for i in dis.hasjabs:
  464.         hasjabs.add(dis.opname[i])
  465.  
  466.     def convertArgs(self):
  467.         """Convert arguments from symbolic to concrete form"""
  468.         assert self.stage == FLAT
  469.         self.consts.insert(0, self.docstring)
  470.         self.sort_cellvars()
  471.         for i in range(len(self.insts)):
  472.             t = self.insts[i]
  473.             if len(t) == 2:
  474.                 opname, oparg = t
  475.                 conv = self._converters.get(opname, None)
  476.                 if conv:
  477.                     self.insts[i] = opname, conv(self, oparg)
  478.         self.stage = CONV
  479.  
  480.     def sort_cellvars(self):
  481.         """Sort cellvars in the order of varnames and prune from freevars.
  482.         """
  483.         cells = {}
  484.         for name in self.cellvars:
  485.             cells[name] = 1
  486.         self.cellvars = [name for name in self.varnames
  487.                          if cells.has_key(name)]
  488.         for name in self.cellvars:
  489.             del cells[name]
  490.         self.cellvars = self.cellvars + cells.keys()
  491.         self.closure = self.cellvars + self.freevars
  492.  
  493.     def _lookupName(self, name, list):
  494.         """Return index of name in list, appending if necessary
  495.  
  496.         This routine uses a list instead of a dictionary, because a
  497.         dictionary can't store two different keys if the keys have the
  498.         same value but different types, e.g. 2 and 2L.  The compiler
  499.         must treat these two separately, so it does an explicit type
  500.         comparison before comparing the values.
  501.         """
  502.         t = type(name)
  503.         for i in range(len(list)):
  504.             if t == type(list[i]) and list[i] == name:
  505.                 return i
  506.         end = len(list)
  507.         list.append(name)
  508.         return end
  509.  
  510.     _converters = {}
  511.     def _convert_LOAD_CONST(self, arg):
  512.         if hasattr(arg, 'getCode'):
  513.             arg = arg.getCode()
  514.         return self._lookupName(arg, self.consts)
  515.  
  516.     def _convert_LOAD_FAST(self, arg):
  517.         self._lookupName(arg, self.names)
  518.         return self._lookupName(arg, self.varnames)
  519.     _convert_STORE_FAST = _convert_LOAD_FAST
  520.     _convert_DELETE_FAST = _convert_LOAD_FAST
  521.  
  522.     def _convert_LOAD_NAME(self, arg):
  523.         if self.klass is None:
  524.             self._lookupName(arg, self.varnames)
  525.         return self._lookupName(arg, self.names)
  526.  
  527.     def _convert_NAME(self, arg):
  528.         if self.klass is None:
  529.             self._lookupName(arg, self.varnames)
  530.         return self._lookupName(arg, self.names)
  531.     _convert_STORE_NAME = _convert_NAME
  532.     _convert_DELETE_NAME = _convert_NAME
  533.     _convert_IMPORT_NAME = _convert_NAME
  534.     _convert_IMPORT_FROM = _convert_NAME
  535.     _convert_STORE_ATTR = _convert_NAME
  536.     _convert_LOAD_ATTR = _convert_NAME
  537.     _convert_DELETE_ATTR = _convert_NAME
  538.     _convert_LOAD_GLOBAL = _convert_NAME
  539.     _convert_STORE_GLOBAL = _convert_NAME
  540.     _convert_DELETE_GLOBAL = _convert_NAME
  541.  
  542.     def _convert_DEREF(self, arg):
  543.         self._lookupName(arg, self.names)
  544.         self._lookupName(arg, self.varnames)
  545.         return self._lookupName(arg, self.closure)
  546.     _convert_LOAD_DEREF = _convert_DEREF
  547.     _convert_STORE_DEREF = _convert_DEREF
  548.  
  549.     def _convert_LOAD_CLOSURE(self, arg):
  550.         self._lookupName(arg, self.varnames)
  551.         return self._lookupName(arg, self.closure)
  552.  
  553.     _cmp = list(dis.cmp_op)
  554.     def _convert_COMPARE_OP(self, arg):
  555.         return self._cmp.index(arg)
  556.  
  557.     # similarly for other opcodes...
  558.  
  559.     for name, obj in locals().items():
  560.         if name[:9] == "_convert_":
  561.             opname = name[9:]
  562.             _converters[opname] = obj
  563.     del name, obj, opname
  564.  
  565.     def makeByteCode(self):
  566.         assert self.stage == CONV
  567.         self.lnotab = lnotab = LineAddrTable()
  568.         for t in self.insts:
  569.             opname = t[0]
  570.             if len(t) == 1:
  571.                 lnotab.addCode(self.opnum[opname])
  572.             else:
  573.                 oparg = t[1]
  574.                 if opname == "SET_LINENO":
  575.                     lnotab.nextLine(oparg)
  576.                     continue
  577.                 hi, lo = twobyte(oparg)
  578.                 try:
  579.                     lnotab.addCode(self.opnum[opname], lo, hi)
  580.                 except ValueError:
  581.                     print opname, oparg
  582.                     print self.opnum[opname], lo, hi
  583.                     raise
  584.         self.stage = DONE
  585.  
  586.     opnum = {}
  587.     for num in range(len(dis.opname)):
  588.         opnum[dis.opname[num]] = num
  589.     del num
  590.  
  591.     def newCodeObject(self):
  592.         assert self.stage == DONE
  593.         if (self.flags & CO_NEWLOCALS) == 0:
  594.             nlocals = 0
  595.         else:
  596.             nlocals = len(self.varnames)
  597.         argcount = self.argcount
  598.         if self.flags & CO_VARKEYWORDS:
  599.             argcount = argcount - 1
  600.         return new.code(argcount, nlocals, self.stacksize, self.flags,
  601.                         self.lnotab.getCode(), self.getConsts(),
  602.                         tuple(self.names), tuple(self.varnames),
  603.                         self.filename, self.name, self.lnotab.firstline,
  604.                         self.lnotab.getTable(), tuple(self.freevars),
  605.                         tuple(self.cellvars))
  606.  
  607.     def getConsts(self):
  608.         """Return a tuple for the const slot of the code object
  609.  
  610.         Must convert references to code (MAKE_FUNCTION) to code
  611.         objects recursively.
  612.         """
  613.         l = []
  614.         for elt in self.consts:
  615.             if isinstance(elt, PyFlowGraph):
  616.                 elt = elt.getCode()
  617.             l.append(elt)
  618.         return tuple(l)
  619.  
  620. def isJump(opname):
  621.     if opname[:4] == 'JUMP':
  622.         return 1
  623.  
  624. class TupleArg:
  625.     """Helper for marking func defs with nested tuples in arglist"""
  626.     def __init__(self, count, names):
  627.         self.count = count
  628.         self.names = names
  629.     def __repr__(self):
  630.         return "TupleArg(%s, %s)" % (self.count, self.names)
  631.     def getName(self):
  632.         return ".%d" % self.count
  633.  
  634. def getArgCount(args):
  635.     argcount = len(args)
  636.     if args:
  637.         for arg in args:
  638.             if isinstance(arg, TupleArg):
  639.                 numNames = len(misc.flatten(arg.names))
  640.                 argcount = argcount - numNames
  641.     return argcount
  642.  
  643. def twobyte(val):
  644.     """Convert an int argument into high and low bytes"""
  645.     assert type(val) == types.IntType
  646.     return divmod(val, 256)
  647.  
  648. class LineAddrTable:
  649.     """lnotab
  650.  
  651.     This class builds the lnotab, which is documented in compile.c.
  652.     Here's a brief recap:
  653.  
  654.     For each SET_LINENO instruction after the first one, two bytes are
  655.     added to lnotab.  (In some cases, multiple two-byte entries are
  656.     added.)  The first byte is the distance in bytes between the
  657.     instruction for the last SET_LINENO and the current SET_LINENO.
  658.     The second byte is offset in line numbers.  If either offset is
  659.     greater than 255, multiple two-byte entries are added -- see
  660.     compile.c for the delicate details.
  661.     """
  662.  
  663.     def __init__(self):
  664.         self.code = []
  665.         self.codeOffset = 0
  666.         self.firstline = 0
  667.         self.lastline = 0
  668.         self.lastoff = 0
  669.         self.lnotab = []
  670.  
  671.     def addCode(self, *args):
  672.         for arg in args:
  673.             self.code.append(chr(arg))
  674.         self.codeOffset = self.codeOffset + len(args)
  675.  
  676.     def nextLine(self, lineno):
  677.         if self.firstline == 0:
  678.             self.firstline = lineno
  679.             self.lastline = lineno
  680.         else:
  681.             # compute deltas
  682.             addr = self.codeOffset - self.lastoff
  683.             line = lineno - self.lastline
  684.             # Python assumes that lineno always increases with
  685.             # increasing bytecode address (lnotab is unsigned char).
  686.             # Depending on when SET_LINENO instructions are emitted
  687.             # this is not always true.  Consider the code:
  688.             #     a = (1,
  689.             #          b)
  690.             # In the bytecode stream, the assignment to "a" occurs
  691.             # after the loading of "b".  This works with the C Python
  692.             # compiler because it only generates a SET_LINENO instruction
  693.             # for the assignment.
  694.             if line >= 0:
  695.                 push = self.lnotab.append
  696.                 while addr > 255:
  697.                     push(255); push(0)
  698.                     addr -= 255
  699.                 while line > 255:
  700.                     push(addr); push(255)
  701.                     line -= 255
  702.                     addr = 0
  703.                 if addr > 0 or line > 0:
  704.                     push(addr); push(line)
  705.                 self.lastline = lineno
  706.                 self.lastoff = self.codeOffset
  707.  
  708.     def getCode(self):
  709.         return ''.join(self.code)
  710.  
  711.     def getTable(self):
  712.         return ''.join(map(chr, self.lnotab))
  713.  
  714. class StackDepthTracker:
  715.     # XXX 1. need to keep track of stack depth on jumps
  716.     # XXX 2. at least partly as a result, this code is broken
  717.  
  718.     def findDepth(self, insts, debug=0):
  719.         depth = 0
  720.         maxDepth = 0
  721.         for i in insts:
  722.             opname = i[0]
  723.             if debug:
  724.                 print i,
  725.             delta = self.effect.get(opname, None)
  726.             if delta is not None:
  727.                 depth = depth + delta
  728.             else:
  729.                 # now check patterns
  730.                 for pat, pat_delta in self.patterns:
  731.                     if opname[:len(pat)] == pat:
  732.                         delta = pat_delta
  733.                         depth = depth + delta
  734.                         break
  735.                 # if we still haven't found a match
  736.                 if delta is None:
  737.                     meth = getattr(self, opname, None)
  738.                     if meth is not None:
  739.                         depth = depth + meth(i[1])
  740.             if depth > maxDepth:
  741.                 maxDepth = depth
  742.             if debug:
  743.                 print depth, maxDepth
  744.         return maxDepth
  745.  
  746.     effect = {
  747.         'POP_TOP': -1,
  748.         'DUP_TOP': 1,
  749.         'SLICE+1': -1,
  750.         'SLICE+2': -1,
  751.         'SLICE+3': -2,
  752.         'STORE_SLICE+0': -1,
  753.         'STORE_SLICE+1': -2,
  754.         'STORE_SLICE+2': -2,
  755.         'STORE_SLICE+3': -3,
  756.         'DELETE_SLICE+0': -1,
  757.         'DELETE_SLICE+1': -2,
  758.         'DELETE_SLICE+2': -2,
  759.         'DELETE_SLICE+3': -3,
  760.         'STORE_SUBSCR': -3,
  761.         'DELETE_SUBSCR': -2,
  762.         # PRINT_EXPR?
  763.         'PRINT_ITEM': -1,
  764.         'RETURN_VALUE': -1,
  765.         'YIELD_VALUE': -1,
  766.         'EXEC_STMT': -3,
  767.         'BUILD_CLASS': -2,
  768.         'STORE_NAME': -1,
  769.         'STORE_ATTR': -2,
  770.         'DELETE_ATTR': -1,
  771.         'STORE_GLOBAL': -1,
  772.         'BUILD_MAP': 1,
  773.         'COMPARE_OP': -1,
  774.         'STORE_FAST': -1,
  775.         'IMPORT_STAR': -1,
  776.         'IMPORT_NAME': 0,
  777.         'IMPORT_FROM': 1,
  778.         'LOAD_ATTR': 0, # unlike other loads
  779.         # close enough...
  780.         'SETUP_EXCEPT': 3,
  781.         'SETUP_FINALLY': 3,
  782.         'FOR_ITER': 1,
  783.         }
  784.     # use pattern match
  785.     patterns = [
  786.         ('BINARY_', -1),
  787.         ('LOAD_', 1),
  788.         ]
  789.  
  790.     def UNPACK_SEQUENCE(self, count):
  791.         return count-1
  792.     def BUILD_TUPLE(self, count):
  793.         return -count+1
  794.     def BUILD_LIST(self, count):
  795.         return -count+1
  796.     def CALL_FUNCTION(self, argc):
  797.         hi, lo = divmod(argc, 256)
  798.         return -(lo + hi * 2)
  799.     def CALL_FUNCTION_VAR(self, argc):
  800.         return self.CALL_FUNCTION(argc)-1
  801.     def CALL_FUNCTION_KW(self, argc):
  802.         return self.CALL_FUNCTION(argc)-1
  803.     def CALL_FUNCTION_VAR_KW(self, argc):
  804.         return self.CALL_FUNCTION(argc)-2
  805.     def MAKE_FUNCTION(self, argc):
  806.         return -argc
  807.     def MAKE_CLOSURE(self, argc):
  808.         # XXX need to account for free variables too!
  809.         return -argc
  810.     def BUILD_SLICE(self, argc):
  811.         if argc == 2:
  812.             return -1
  813.         elif argc == 3:
  814.             return -2
  815.     def DUP_TOPX(self, argc):
  816.         return argc
  817.  
  818. findDepth = StackDepthTracker().findDepth
  819.